As the compression/expansion technique for a multi-level image, the JPEG system has so far been routinely used. The JPEG 2000 system, aimed at improving the image quality at a further ultra-low bit rate, has been developed, and expectations are made of this new system as being a high compression multi-function next-generation compression/expansion system for a wide field of application more favorable than the JPEG system. In particular, notice is stirred up in the field of a digital camera, facsimile and copying apparatus or a combination apparatus thereof.
Thus, the JPEG 2000 system is thought to be promising in the perspective of future utilization. However, technical difficulties are met in that, due to algorithm-related constraints, processing is more complex than in the conventional JPEG system, with the processing time being several times as long as that needed in the conventional JPEG system. In particular, long processing time in a bit modeling unit poses a serious problem.
The schematics of the processing by the JPEG2000 system are hereinafter explained. FIG. 10 shows the overall processing flow of the JPEG2000 system.
An input multi-level image 10-1 is subjected to wavelet transform 10-2, the resulting transform coefficients are subjected to quantization 10-3 and the quantized transform coefficients are processed with entropy coding 10-4 which generates output codes termed a codestream 10-5.
In the entropy coding 10-4, bit modeling processing 10-6 and arithmetic encoding processing 10-7 are executed. A unit of the image processed in the bit modeling processing 10-6 is a block of transform coefficients having a size of powers of 2 in each of the horizontal (vertical and horizontal) directions and the vertical direction, with the contents of the transform coefficients comprising positive and negative signs and absolute values of the quantized transform coefficients.
The processing during image compression is from left to right direction in FIG. 10, while that during image expansion is in an opposite direction, that is, from right to left direction. However, the procedure for bit modeling is not changed for compression and expansion. Thus, the following explanation is made for the compression side as the basis.
The overall processing contents of the JPEG 2000 system are stated in detail in ISO/IECI 5444-1, “JPEG2000 image coding system-part1: Core coding system”.
In the JPEG2000 system, in distinction from the JPEG system, the entire processing is not executed to the same size range, but the wavelet transform and quantization are executed in a size range termed a tile.
In the next entropy coding, processing is executed with a code block (CB) 11-1, shown in FIG. 11, as a unit. The bit modeling processing is carried out with a two-dimensional bit plane 9-6 as a unit. The bit plane is obtained on resolving an absolute value 11-5, shown in FIG. 11, on the bit-by-bit basis, beginning from the MSB.
FIG. 12, shows the processing sequence within the bit plane. In FIG. 12, four transform coefficients, processed by one scanning in the vertical direction, are termed four vertical coefficients.
The bit modeling processing is now explained in detail. On a bit plane 11-6, the one transform coefficient, currently processed, of the four vertical coefficients, which are processed in the sequence shown in FIG. 12, is called a target coefficient 11-2. In the following, the bit in the target coefficient 11-2 lying in the bit plane being processed is called a current bit 11-3.
In the bit modeling processing, the context value of the current bit is calculated as indicating the feature of the image of the target coefficient. In this case, eight neighbor bits around the current bit are referenced for calculating the context value. FIG. 13 shows a context model composed of a current bit 13-1 and eight neighbor bits 13-2.
In the bit modeling processing, the absolute value 11-5 of the coefficient shown in FIG. 11 and the sign (plus or minus) of the coefficient are processed differentially. Specifically, the absolute value is processed on the bit plane basis and if, in this processing process, the target coefficient 11-2 is verified to be other than 0, the sign (plus or minus) is also processed.
If, for example, the coefficient following the wavelet transform is represented by 8 bits, the absolute value is represented by 7 bits, while the sign (plus or minus) is represented by 1 bit. For processing, eight processing operations are needed per coefficient at the maximum.
That is, in the JPEG2000 system, in distinction from the JPEG system, bit modeling processing is performed on the bit plane basis, so that the processing quantity for bit modeling processing is increased.
Referring to flowcharts of FIGS. 14 to 21, the bit modeling processing is explained. It is noted that the present invention is not concerned with the processing procedure of the bit modeling itself, but is principally aimed to optimize the memory storage method and the address generation, to reduce the number of access operations by the addition of registers and to improve the performance. Consequently, the flowcharts show simply the processing sequence relevant to this object. These are associated with any of the arrangements of FIGS. 1, 3, 22 and 24.
Meanwhile, in FIGS. 14 to 22, double dotted line blocks indicate the read and write for the associated respective memories.
FIG. 14 shows the bit modeling processing in its entirety and specifically shows the CB-based processing.
In the bit model processing unit, executing the bit modeling processing, the current bit, included in the SIG (significance propagation pass) of the bit plane, is calculated form the condition, and the processing shown in FIGS. 15 and 16 is carried out.
Then, a current bit of a coefficient, not included in the SIG pass, and which is included in the condition of the MAG (magnitude refinement pass) pass, is processed, in accordance with the flowchart shown in FIGS. 15 and 16.
Finally, the current bits, not as yet processed, are processed as the CLN (cleanup pass), in accordance with the flowchart shown in FIGS. 18 to 21.
These three passes are termed a three-pass processing. For the processing conditions, significance information, sign (plus or minus) information, refinement information and processed information, are needed.
The significance information is the information which becomes “1” when the target coefficient 11-2 shown in FIG. 11 is determined to be other than 0. The sign (plus or minus) information is the information which becomes “1” when the target coefficient 11-2 shown in FIG. 11 is verified to be a negative coefficient. The refinement information is the information which becomes “1” when the processing of the MAG pass has come to a close and the processed information is the information which becomes “1” when the processing of the current bit in the bit plane has come to a close.
In the bit modeling processing, shown in FIG. 14, a significance information memory, a plus/minus sign memory and a refinement information memory are initialized in a step S101.
A step S102 is a loop (iteration) of a bit number of the absolute value of the wavelet coefficient. In the step S102, a loop counter(not shown) is counted down in a direction from the MSB to the LSB.
In a step S103, the processed information memory is initialized.
In a step S104, since there is a condition that, in the bit modeling processing, the first bit plane is to begin the processing from the CLN pass, it is verified whether or not a given bit plane is the first bit plane. If the given bit plane is the MSB (first bit plane), processing is carried out as from a step S107 and, if otherwise, the processing is carried out as from a step S105.
The step S105 is a processing of the SIG pass which is shown in detail in the flowcharts of FIGS. 15 and 16.
The step S106 is a processing of the MAG pass which is shown in detail in the flowcharts of FIG. 17.
The step S107 is a processing of the CLN pass which is shown in detail in the flowcharts of FIGS. 15 and 16.
FIGS. 15 and 16 show flowcharts showing the processing of the SIG pass and show detailed operation of the step S105 shown in FIG. 14.
A step S201 is a loop (iteration) in the vertical direction of the CB size, with an increment being 4. Thus, if the vertical size of the CB size is 64 pixels, a loop counter (not shown) counts up 0, 4, 8, 16, . . . .
A step S202 is a loop (iteration) in the horizontal direction of the CB size, with the count value becoming the horizontal coordinate of the coefficient being processed.
A step S203 is a loop (iteration) of the vertical four coefficients. The loop count value of step S201 and the count value of the step S203, combined together, become the vertical coordinate of the coefficient being processed.
In a step S204, the significance information of the current bit and the eight neighbor bits are read from the significance information memory, in accordance with the addresses calculated from the vertical and horizontal coordinates, specified by the loop counters (not shown) of steps S201 to S203.
If, in a next step S205, a value at a location corresponding to the current bit in the significance information being read is “1” (in this case, the current bit is retained to be significant), processing is not made in the SIG pass. Thus, the next following passes are skipped and processing goes back to the step S203.
If, in a step S206, a value at any one of locations corresponding to the eight neighbor pixels of the significance information being read is “1” (in this case, the one of the eight neighbor pixels is retained to be significant, the processing of a step S207 is carried out to output the context of the target bit. If all of the eight neighbor pixels are zero, in which case the eight neighbors are all retained to be insignificant, the next following processing is skipped to go back to the step S203.
In a next step S207, from the SIG context model of the eight neighbor pixels shown in the following Table 1:
TABLE 1Sum ofhorizontalSum of verticalSum of diagonalContext valuesignificancesignificancesignificance(output value)2any numberany number811 or moreany number7101 or more6100502any number401any number3002 or more200110000
the context values of the target bit are found and output as the results the bit model processing.
In the above Table 1, the vertical direction denotes V0 and V1 in the eight neighbor pixels 13-2 in the context model shown in FIG. 13, while the horizontal direction denotes H0 and H1 in the eight neighbor pixels 13-2 in the context model shown in FIG. 13. The diagonal direction denotes D0, D1, D2 and D3 in the eight neighbor pixels 13-2 in the context model shown in FIG. 13.
The context values are formed by the number of the significance conditions in the respective directions. The context values denote the features of an image as calculated from the conditions of the eight neighbor pixels 13-2.
In a next step S208, the transform coefficient is read from the transform coefficient storage memory. In a step S209, the sign (plus or minus) of the transform coefficient read is also output as a result of the bit modeling processing.
If, at a step S210, the current bit is “0”, steps S211 to S214 are skipped.
If, in the step S210, the current bit is “1”, the transform coefficient is verified to be other than 0, so that, in the next step S211, the information as to the sign (plus or minus) of the eight neighbor pixels of the current bit is read from the plus/minus sign memory.
In a step S212, from the context model of the sign (plus or minus) shown in the following Table 2:
TABLE 2DecisionV0 or HOV1 or H1valueSignificance coefficientSignificance coefficient1(plus)(plus)Significance coefficientSignificance coefficient0(minus)(plus)Insignificance coefficientSignificance coefficient1(plus)Significance coefficientSignificance coefficient0(plus)(minus)Significance coefficientSignificance coefficient−1(minus)(minus)Insignificance coefficientSignificance coefficient−1(minus)Significance coefficientInsignificance coefficient1(plus)Significance coefficientInsignificance coefficient−1(minus)Insignificance coefficientInsignificance coefficient0Horizontal decisionContext valuevalueVertical decision value(output value)111310121−11101100090−110−1111−1012−1−113
the context of the sign (plus or minus) is found and output as the results of the bit modeling processing.
In a next step S213, the sign (plus or minus) is found from the transform coefficient read out from the previous step S208 to output the results as being the results of the bit modeling processing.
In a step S214, the sign (plus or minus) as found from the target coefficients is written in the current bit of the plus/minus sign memory.
Similarly, “1” (indicative of being significant) is written in a step S215 in the data corresponding to the current bit of the significance information memory.
Similarly, “1” (indicative of being significant) is written in a step S216 in the processed memory.
FIG. 17 is a flowchart showing the processing of the MAG pass, and shows the detailed operation of the step S106 shown in FIG. 14.
A step S301 is a loop (iteration) in the vertical direction of the CB size, with an increment being 4. Thus, if the vertical size of the CB size is 64 pixels, a loop counter (not shown) is counted up 0, 4, 8, 16, . . . .
A step S302 is a loop (iteration) in the horizontal direction of the CB size. The loop count value of the step S302 is the horizontal coordinate of the processing coefficients.
A step S303 is a loop (iteration) of the vertical four coefficients. The loop count value of step S301 and the count value of the step S303, combined together, become the vertical coordinate of the processing coefficient.
In a step S304, in accordance with addresses calculated from the vertical and horizontal coordinates specified by the loop counters of steps S301 to S303, the significance information of the current bit is read from the significance information memory and the processed information of the current bit is read from the processed memory.
In steps S305 to S306, if the current coefficient is insignificant, or if “1” (indicating ‘processed’) is set in the processed information, following steps S307 to S312 are skipped.
In a step S307, the significance information of the eight surrounding pixels of the current bit is read. In a step S308, from a MAG context model of the eight surrounding pixels, shown in the following table 3:
TABLE 3Sum of contribution ofRefinementContext valueeight neighborsinformation(output value)any number116except 00150014
the context of the target bit is obtained and output as a result of the bit processing modeling.
In a step S309, the transform coefficients are read from the transform coefficient storage memory and, in a step S310, the sign (plus or minus) of the transform coefficient read is also output as a result of the bit modeling processing.
In a step S311, “1” (indicating ‘refined’) is written in data corresponding to the current bit in the refinement information memory.
Similarly, in a step S312, “1” (indicating ‘processed’) is written in the processed memory.
FIGS. 18 to 21 depict flowcharts showing the processing of the CLN pass and illustrate a detailed operation of the step S107 shown in FIG. 16.
A step S401 is a loop (iteration) in the vertical direction of the CB size, with an increment being 4. Thus, if the vertical size of the CB size is 64 pixels, a loop counter (not shown) is counted up 0, 4, 8, 16, . . . .
A step S402 is a loop in the horizontal direction of the CB size, with the count value becoming the horizontal coordinate of the coefficient being processed.
In a step S403, the significance information of respective current bits of the vertical four coefficients and the eight neighbor pixels are read from the significance information memory, in accordance with the addresses calculated from the vertical and horizontal coordinates indicated by loop counters (not shown) of steps S401 and S402.
Similarly, in a step S404, the processed information of the vertical four coefficients is read from the processed information memory.
If, in a step S405, the processed information of the four vertical coefficients is all “0”, and the significance information of the eight neighbors of the current bits of the four vertical coefficients is all insignificant, the processing as from step S408 is carried out. If otherwise, processing transfers to a step S406.
In the step S406, the number of processing loop iteration of a step S407 is set to 4. This indicates that the processing similar to the SIG pass processing is carried out for all of the vertical four coefficients.
In a step S407, the context values are generated. The detailed flowchart of FIGS. 20 and 21 show the detailed operation.
In a step S408, if the current bits of the vertical four coefficients are all “0”, then the processing as from step S413 is carried out. If otherwise, the processing of a step S409 is carried out.
In a step S409, one of the current bits of the vertical four coefficients is “1”, so that the context specifying that not all of the current bits of the vertical four coefficients are “0” is first output and, in the next step S410, a codeword “1” is output.
In the next step S411, a run length representing the positions of “1” of the vertical four coefficients by a numerical figure of from 0 to 3 is found.
In the next step S412, the context of the run length and the code for the run length composed of two bits is output.
In a step S413, where all of the vertical four coefficients are “0”, a context specifying this is output. A codeword “0” is output in a step S414.
The detailed flowchart of FIGS. 20 and 21 is now explained.
A step S415 is a loop (iteration) of a (4-run length) number of times. More specifically, when the processed information of the vertical four coefficients, representing the condition of the step S405, is all “0” and not all of the significance information of eight neighbors of the current bits of the vertical four coefficients are insignificant, four number of iterations are carried out.
If the run length is found in the steps S409 ff., one of the current bits is “1”. Thus, in order to encode the vertical current bits as from the time of the occurrence of the “1”, a number of times equal to (4-run length) of iterations is carried out.
In the next step S416, the leading end of the run is checked. This check is that as to whether or not, when one of the current bits of the vertical four coefficients is “1”, the current bit has become “1” for the first time. If the bit in question is the leading end bit, a step S417 is executed and, if otherwise, a step S423 is executed.
If the bit in question is the leading end of the run, the information on the sign (plus or minus) of the eight neighbors of the current bit is read out in the step S417 from the plus/minus sign memory.
In the next step S418, the context value is found from the context model shown in the Table 2 and output as a result of the bit modeling processing.
In the next step S419, the sign (plus or minus) of the target coefficient is read from the memory for storage of the transform coefficients. In a step S420, the sign (plus or minus) is also output as the results of the bit model processing.
In a step S421, the sign (plus or minus) as found from the target coefficient is written in the current bit of the plus/minus sign memory.
Similarly, in a step S422, “1” (indicating being significant) is written in a significance information memory as well.
In the next step S424, the context value is found from the context model shown in the Table 1 and output as a result of the bit model processing.
In the next step S425, the transform coefficient is read from the transform coefficient storage memory and, in a step S426, the sign of the transform coefficient is also output as a result of the bit model processing.
If, in a step S427, the current bit is “0”, the steps S428 to S432 are skipped.
If the current bit is “1”, it is found that the transform coefficient is different from 0. Thus, in the next step S428, the sign (plus or minus) information of the eight surrounding bits of the current bit is read from the plus/minus sign memory.
In a step S429, the context value is found from the context model shown in the Table 2 and output as a result of the bit modeling processing. In a step S430, the sign (plus or minus) is similarly output as a result of the bit modeling processing.
In a step S431, the sign (plus or minus) as found from the current coefficient is written in the current bit of the plus/minus sign memory. Similarly, in a step S432, “1” (indicating being significant) is written in the significance information memory.
The structure of the conventional multi-level image encoding/decoding apparatus and the memory accessing operation thereof are hereinafter explained.
First Conventional Art
FIG. 22 is a block diagram showing the structure of a first conventional art of a multi-level image encoding/decoding apparatus and FIG. 23 shows a memory structure of the first conventional art.
The multi-level image encoding/decoding apparatus of the conventional art includes a transform coefficient storage memory 1, a significance information memory 2, a plus/minus sign memory 3, a processed information memory 4, a refinement information memory 5, a bit modeling unit 6, and an arithmetic encoder 7, as shown in FIG. 22. The bit modeling unit 6 includes an address generator 100.
FIG. 23A shows a memory map of each memory and FIG. 23B shows an array on the code block of the information of each memory.
The transform coefficient storage memory 1 stores the transform coefficients of the result of wavelet transform. The significance information memory 2 stores the information as to the sign (plus or minus) of the transform coefficient. The plus/minus sign memory 3 stores the sign (plus or minus) information of the transform coefficient. The processed information memory 4 stores the information as to whether or not the transform coefficient has been processed with bit modeling. The refinement information memory 5 stores the information indicating whether or not the processing of the MAG pass of the transform coefficients has come to a close.
Using the addresses of the vertical and horizontal coordinates of the bit modeling processing, generated in the address generator 100, the bit modeling unit 6 performs bit modeling processing on the information read by accessing each memory to output the information of the result of the processing (context (CX) and sign). Using the information of the processing result (context and sign) of the bit modeling unit 6, the arithmetic encoder 7 generates and outputs the compressed image information.
Using data of the bit length equal to the code block size from the significance information memory 2, plus/minus sign memory 3, processed information memory 4 and the refinement information memory 5, the bit modeling unit 6 performs bit modeling processing on the transform coefficient from the transform coefficient storage memory 1.
More specifically, a 1 bit×4096 word memory is required, solely for the significance information, in case the code block size is of 64×64=4096 (=1000h), as shown in FIG. 23. However, since the memory of the same information quantity is needed for each of the significance information memory 2, plus/minus sign memory 3, processed information memory 4 and the refinement information memory 5, four memories each being of 4096 words×1 bit are required for the apparatus in its entirety. Moreover, a 64×64×(bit precision length of the transform coefficient) is required for the transform coefficient storage memory 1.
In this case, in calculating the context of the SIG pass processing, shown in the flowchart of FIGS. 15 and 16, nine read accesses in the step S204, one read access in the step S208, eight read accesses in the step S211, one write access in the step S214, one write access in the step S215, and one write access in the step S216, are required, so that, in the SIG pass processing, 21 accesses at the maximum are required.
Similarly, in the MAG pass processing, shown in the flowchart of FIG. 17, one read access in the step S304, eight read accesses in the step S307, one read access in the step S309, one write access in the step S311 and one write access in the step S312, are required, so that 12 accesses operations at the maximum are required for the MAG pass processing.
Although the detailed explanation is omitted for the CLN pass processing, 8 memory accesses at the maximum are required for obtaining the information of the eight neighbor pixels in the memory structure shown in FIG. 23.
Second Conventional Art
FIG. 24 is a block diagram showing the structure of a second conventional art of a multi-level image encoding/decoding apparatus, and FIG. 25 shows a memory map of the second conventional art.
The multi-level image encoding/decoding apparatus of this conventional art includes a transform coefficient storage memory 1, a bit modeling unit 6, an arithmetic encoder 7 and a memory for variety of information 8, as shown in FIG. 24. Of these, the transform coefficient storage memory 1 and the arithmetic encoder 7 are the same as those of the first conventional art shown in FIG. 22.
The memory for a variety of information 8 includes, in one 20-bit word, the significance information 25-1 of eight neighbors, the significance information 25-2 of the current bit, the sign (plus and minus) 25-3 of eight neighbors, the sign (plus and minus) 25-4 of the current bit, the refinement information 25-5 and the processed information 25-6.
The processing in the bit modeling unit 6, shown in FIG. 24, employing the memory for a variety of information 8, shown in FIG. 25, is the processing executed in a program (JASPER version 1.500.3 in WEB site: http://www.ece.ubc.ca/-mdadams/jasper/ stated in the C language for recognition of the JPEG 2000 operation, termed JASPER.